#include <iostream>
#include <chrono>
#include <malloc.h>
#include <xmmintrin.h>

using namespace std;

void* aligned_malloc(size_t size, size_t alignment) {
    void* p;
    posix_memalign(&p, alignment, size);
    return p;
}

void aligned_free(void* p) {
    free(p);
}

const int n[10] = {96, 192, 304, 400, 496, 608, 704, 800, 896, 992};
const int m[10] = {96, 192, 304, 400, 496, 608, 704, 800, 896, 992};
const int p[10] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};

int lp(int *A, int size) {
    int x = size - 1;
    int count = 0;
    while (!A[count]) {
        x--;
        count++;
    }
    return x;
}

int main() {
    for (int k = 0; k < 10; k++) {
        int* R = (int*)aligned_malloc(16 * n[k] * n[k], 16);
        int* E = (int*)aligned_malloc(16 * n[k] * n[k], 16);

        for (int i = 0; i < n[k]; i++) {
            for (int j = 0; j < n[k]; j++) {
                R[i * n[k] + j] = 0;
                E[i * n[k] + j] = 0;
            }
        }

        for (int i = 0; i < m[k]; i++) {
            for (int j = n[k] - p[k]; j < n[k]; j++) {
                E[i * n[k] + j] = 1;
            }
        }

        for (int i = 0; i < p[k]; i++) {
            R[i * n[k] + n[k] - i - 1] = 1;
        }

        auto t1 = chrono::high_resolution_clock::now();

        for (int i = 0; i < m[k]; i++) {
            int IsNull = 0;
            __m128i IsNullHelp = _mm_setzero_si128();

            for (int j = 0; j + 4 < n[k]; j += 4) {
                __m128i IsNullHelpE = _mm_load_si128((__m128i_u*)&E[i * n[k] + j]);
                IsNullHelp = _mm_or_si128(IsNullHelp, IsNullHelpE);
            }

            int* temp = (int*)&IsNullHelp;
            IsNull |= temp[0] | temp[1] | temp[2] | temp[3];

            while (IsNull) {
                int IsNull2 = 0;
                __m128i IsNull2Help = _mm_setzero_si128();

                for (int j = 0; j + 4 < n[k]; j += 4) {
                    __m128i IsNull2HelpR = _mm_load_si128((__m128i_u*)&R[lp(&E[i * n[k]], n[k]) * n[k] + j]);
                    IsNull2Help = _mm_or_si128(IsNull2Help, IsNull2HelpR);
                }

                temp = (int*)&IsNull2Help;
                IsNull2 |= temp[0] | temp[1] | temp[2] | temp[3];

                if (IsNull2) {
                    int FirstNum = lp(&E[i * n[k]], n[k]);
                    for (int j = 0; j + 4 < n[k]; j += 4) {
                        __m128i vtE = _mm_load_si128((__m128i_u*)&E[i * n[k] + j]);
                        __m128i vtR = _mm_load_si128((__m128i_u*)&R[FirstNum * n[k] + j]);
                        vtE = _mm_xor_si128(vtE, vtR);
                        _mm_store_si128((__m128i_u*)&E[i * n[k] + j], vtE);
                    }
                } else {
                    int FirstNum = lp(&E[i * n[k]], n[k]);
                    for (int j = 0; j + 4 < n[k]; j += 4) {
                        _mm_store_si128((__m128i_u*)&R[FirstNum * n[k] + j], _mm_load_si128((__m128i_u*)&E[i * n[k] + j]));
                        _mm_store_si128((__m128i_u*)&E[i * n[k] + j], _mm_setzero_si128());
                    }
                    break;
                }

                IsNull = 0;
                IsNullHelp = _mm_setzero_si128();

                for (int j = 0; j + 4 < n[k]; j += 4) {
                    __m128i IsNullHelpE = _mm_load_si128((__m128i_u*)&E[i * n[k] + j]);
                    IsNullHelp = _mm_or_si128(IsNullHelp, IsNullHelpE);
                }

                temp = (int*)&IsNullHelp;
                IsNull |= temp[0] | temp[1] | temp[2] | temp[3];
            }
        }

        auto t2 = chrono::high_resolution_clock::now();
        chrono::duration<double, std::milli> fp_ms = t2 - t1;
        auto int_ms = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1);
        std::chrono::duration<long, std::micro> int_usec = int_ms;

        std::cout << k + 1 << "00: " << fp_ms.count() / 1000.0 << "s" << endl;

        aligned_free(E);
        aligned_free(R);
    }

    return 0;
}
